Busy Beaver
A HALTING, BINARY-ALPHABET TURING MACHINE WHICH WRITES THE MOST 1S ON THE TAPE, USING ONLY A LIMITED SET OF STATES
Busy Beaver; Busy beaver function; Busy beaver problem; Busy Beaver function; Busy Beaver problem; Busy Beaver Problem; Busy Beaver Number; Maximum shifts function; Busy-beaver; N-state busy beaver game; BB-n game; Generalized busy beaver functions; Busy Beaver game
<
theory> (BB) One of a series of sets of
Turing Machine
programs. The BBs in the Nth set are programs of N states
that produce a larger finite number of ones on an initially
blank tape than any other program of N states. There is no
program that, given input N, can deduce the productivity
(number of ones output) of the BB of size N.
The productivity of the BB of size 1 is 1. Some work has been
done to figure out productivities of bigger Busy Beavers - the
7th is in the thousands.
(1994-10-24)